package algorithm;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

/**
 * 145. 二叉树的后序遍历
 * @author Panbo Guo
 * @date 2021/7/15
 */
public class T00145 {

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1,2,3,4,5,null,6,null,null,7};
        System.out.println(new Solution().postorderTraversal(TreeUtils.buildTree(arr)));
    }

    static class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if (root != null) {
                Stack<TreeNode> stack = new Stack<>();
                Set<TreeNode> flagSet = new HashSet<>();
                for (TreeNode cur = root; ;) {
                    if (cur == null) {
                        if (stack.isEmpty()) break;
                        cur = stack.peek();
                        if (flagSet.contains(cur)) {
                            list.add(cur.val);
                            flagSet.remove(cur);
                            stack.pop();
                            cur = null;
                            continue;
                        }
                        if (cur.right == null) {
                            list.add(cur.val);
                            stack.pop();
                            cur = null;
                        } else {
                            flagSet.add(cur);
                            cur = cur.right;
                        }
                    } else {
                        stack.push(cur);
                        cur = cur.left;
                    }
                }
            }
            return list;
        }
    }
}
